|
Van der Waerden's theorem is a theorem in the branch of mathematics called Ramsey theory. Van der Waerden's theorem states that for any given positive integers ''r'' and ''k'', there is some number ''N'' such that if the integers are colored, each with one of ''r'' different colors, then there are at least ''k'' integers in arithmetic progression all of the same color. The least such ''N'' is the Van der Waerden number ''W''(''r'', ''k''). It is named after the Dutch mathematician B. L. van der Waerden. For example, when ''r'' = 2, you have two colors, say red and blue. ''W''(2, 3) is bigger than 8, because you can color the integers from like this: and no three integers of the same color form an arithmetic progression. But you can't add a ninth integer to the end without creating such a progression. If you add a red 9, then the red 3, 6, and 9 are in arithmetic progression. Alternatively, if you add a blue 9, then the blue 1, 5, and 9 are in arithmetic progression. In fact, there is no way of coloring 1 through 9 without creating such a progression. Therefore, ''W''(2, 3) is 9. It is an open problem to determine the values of ''W''(''r'', ''k'') for most values of ''r'' and ''k''. The proof of the theorem provides only an upper bound. For the case of ''r'' = 2 and ''k'' = 3, for example, the argument given below shows that it is sufficient to color the integers with two colors to guarantee there will be a single-colored arithmetic progression of length 3. But in fact, the bound of 325 is very loose; the minimum required number of integers is only 9. Any coloring of the integers will have three evenly spaced integers of one color. For ''r'' = 3 and ''k'' = 3, the bound given by the theorem is 7(2·37 + 1)(2·37·(2·37 + 1) + 1), or approximately 4.22·1014616. But actually, you don't need that many integers to guarantee a single-colored progression of length 3; you only need 27. (And it is possible to color with three colors so that there is no single-colored arithmetic progression of length 3; for example, RRYYRRYBYBBRBRRYRYYBRBBYBY.) Anyone who can reduce the general upper bound to any 'reasonable' function can win a large cash prize. Ronald Graham has offered a prize of US$1000 for showing ''W''(2,''k'')<2''k''2. The best upper bound currently known is due to Timothy Gowers, who establishes : by first establishing a similar result for Szemerédi's theorem, which is a stronger version of Van der Waerden's theorem. The previously best-known bound was due to Saharon Shelah and proceeded via first proving a result for the Hales–Jewett theorem, which is another strengthening of Van der Waerden's theorem. The best lower bound currently known for is that for all positive we have , for all sufficiently large . == Proof of Van der Waerden's theorem (in a special case) == The following proof is due to Ron Graham and B.L. Rothschild. Khinchin〔 〕 gives a fairly simple proof of the theorem without estimating ''W''(''r'', ''k''). We will prove the special case mentioned above, that ''W''(2, 3) ≤ 325. Let ''c''(''n'') be a coloring of the integers . We will find three elements of in arithmetic progression that are the same color. Divide into the 65 blocks , , ... , thus each block is of the form for some ''b'' in . Since each integer is colored either red or blue, each block is colored in one of 32 different ways. By the pigeonhole principle, there are two blocks among the first 33 blocks that are colored identically. That is, there are two integers ''b''1 and ''b''2, both in , such that : ''c''(5''b''1 + ''k'') = ''c''(5''b''2 + ''k'') for all ''k'' in . Among the three integers 5''b''1 + 1, 5''b''1 + 2, 5''b''1 + 3, there must be at least two that are of the same color. (The pigeonhole principle again.) Call these 5''b''1 + ''a''1 and 5''b''1 + ''a''2, where the ''a''''i'' are in and ''a''1 < ''a''2. Suppose (without loss of generality) that these two integers are both red. (If they are both blue, just exchange 'red' and 'blue' in what follows.) Let ''a''3 = 2''a''2 − ''a''1. If 5''b''1 + ''a''3 is red, then we have found our arithmetic progression: 5''b''1 + ''a''''i'' are all red. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Van der Waerden's theorem」の詳細全文を読む スポンサード リンク
|